// 有一堆长方体积木，它们的长度和宽度都相同，但长度不一。

// 小橙想把这堆积木叠成一面墙，墙的每层可以放一个积木，也可以将两个积木拼接起来，要求每层的长度相同。

// 若必须用完这些积木，叠成的墙最多为多少层？

// 如下是叠成的一面墙的图示，积木仅按宽和高所在的面进行拼接。
// 输入描述：

// 输入为一行，为各个积木的长度，数字为正整数，并由空格分隔。积木的数量和长度都不超过5000。

// 输出描述：

// 输出一个数字，为墙的最大层数，如果无法按要求叠成每层长度一致的墙，则输出-1。

// 输入

// 给定积木的长度，以空格分隔，例如:3 6 6 3。

// 输出

// 如果可以搭建，返回最大层数，如果不可以返回-1。

// 示例1   输入输出示例仅供调试，后台判题数据一般不包含示例

// 输入

// 3 6 3 3 3

// 输出

// 3

// 解释：以 6 为底的墙，第一层为 6 ，第二层为 3 + 3，第三层 3 + 3。

// 示例2   输入输出示例仅供调试，后台判题数据一般不包含示例

// 输入

// 9 9 9 5 3 2 2 2 2 2

// 输出

// 5

// 解释：

// 5+2+2=9

// 3+2+2+2=9

// 9,9,9

// 共五层

// 背包问题，首先计算和sum，排序，选取最大的maxVal作为墙的第一层，

// 如果 sum % maxVal == 0，代表可以这样划分，

// 如果不可以则 maxVal += maxVal + nuns[i], 加上最小的。

// 可以化分的层数就为 cnt = sum / maxVal

// 背包容量为：sum /= cnt。

function getLayerNum(str) {
    let arr = str.split(" ").map((e) => parseInt(e)).sort((a, b) => a - b);
    let total = arr.reduce((pre, cur) => pre + cur);
    let n = arr.length;
    let max = arr[arr.length - 1]
    for (let i = 0; i < arr.length - 1; i++) {
        if (total % max === 0) {
            break;
        } else {
            max += arr[i]
        }
    }
    let layerNumber = total / max;
    total /= layerNumber;

    const dp = Array.from({ length: n + 1 }, () => {
        return new Array(total + 1).fill(false)
    });
    for (let i = 0; i <= arr.length; i++) {
        dp[i][0] = true;
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= total; j++) {
            if (j - arr[i - 1] < 0) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]]
            }
        }
    }
    if (dp[n][total] === true) {
        console.log(layerNumber)
    } else {
        console.log(-1)
    }
}
getLayerNum('9 9 9 5 3 2 2 2 2 2');
// getLayerNum('3 6 3 3 3');